package com.dhu.graph.commonGrpaph.cycleAndBinary;

import com.dhu.graph.basic.GraphImpls.Graph;

/**
 * @Author ：snow
 * @Date ：Created in 2020-04-23
 * @Description： 把一个图的所有顶点染成两种颜色，能使使得每一条两端的颜色都不相同？等价于这是否是一个二分图
 * @Modified By：
 * @Version:
 */
public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean hasTwoColor;

    public TwoColor(Graph G){
        this.marked = new boolean[G.getVertexes()];
        this.hasTwoColor = true;
        for (int s = 0; s < G.getVertexes(); s++){
            if(marked[s])
                dsf(G, s);
        }
    }

    /**
     * 深度优先搜索遍历图中的顶点，对还未标记的顶点标记并让其颜色与父顶点（前一个顶点）的颜色相反，如果遇到已经标记了的子顶点
     * 颜色和父顶点颜色相同，那么说明这不是一个二分图
     * @param G
     * @param s
     */
    private void dsf(Graph G, int s){
        marked[s] = true;
        for (Integer w : G.adj(s)) {
            if(!marked(w))
            {
                dsf(G,w);
                color[w] = !color[s];

            }
            else if(color[w] == color[s]) hasTwoColor = false;
        }
    }
    private boolean marked(int v){
        return marked[v];
    }
    public boolean isBipartite(){
        return hasTwoColor;
    }
}
